package com.cqs.leetcode;

import com.cqs.leetcode.ds.ArraysUtils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Author:li
 * <p>
 * create date: 18-6-9 07:41
 */
public class Subsets78 {


    // 5ms
    public List<List<Integer>> subsets(int[] nums) {
        final List<List<Integer>> result = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
//        result.add(list);
        if (nums == null || nums.length == 0) return result;
        Arrays.sort(nums);
        ArraysUtils.print(nums);
        next(list, nums, result);
        return result;
    }

    //每次新增一个元素
    private void next(List<Integer> list, int[] nums, final List<List<Integer>> result) {
        result.add(new ArrayList<>(list));
        for (int i = list.size(); i < nums.length; i++) {
            if (list.size() > 0 && list.get(list.size() - 1) >= nums[i]) continue;
            int idx = list.size();
            list.add(nums[i]);
            next(list, nums, result);
            list.remove(idx);
        }
    }

    private void next(final List<List<Integer>> result, List<Integer> list, boolean[] visited) {
        if (list.size() > 0) {
            result.add(new ArrayList<>(list));
            for (int i = 0; i < list.size(); i++) {
                if (!visited[i]) {
                    Integer tmp = list.remove(i);
                    visited[i] = true;
                    next(result, list, visited);
                    list.add(i, tmp);
                    visited[i] = false;
                }
            }
        }
    }

    public static void main(String[] args) {
        Subsets78 ss = new Subsets78();
        int[] nums = {3, 2, 5, 7, 19, 6};
        List<List<Integer>> subsets = ss.subsets(nums);
        System.out.println(subsets);
        System.out.println(Math.pow(2, nums.length));
        System.out.println(subsets.size());
    }

    //3ms
    private class Solution {
        public List<List<Integer>> subsets(int[] nums) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            int len = nums.length;
            addSubset(result, new ArrayList<Integer>(), 0, nums);
            return result;
        }

        void addSubset(List<List<Integer>> result, List<Integer> list, int start, int[] nums) {
            result.add(new ArrayList<Integer>(list));
            for (int i = start; i < nums.length; i++) {
                list.add(nums[i]);
                addSubset(result, list, i + 1, nums);
                list.remove(list.size() - 1);
            }
        }
    }
}
